/*!
 Temelia - AVL tree interface.

 Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#ifndef AVL_TREE_H_
#define AVL_TREE_H_

#include "platform.h"
#include "binary_tree_common.h"

struct _avl_tree_node_t;
typedef struct _avl_tree_node_t *avl_tree_node_t;

/*!
 * @brief Returns the key in current avl tree node.
 * An AVL tree node is the key kept into a binary search tree.
 * Complexity O(1)
 *
 * @param AVL tree node
 */
DECLSPEC void *avl_tree_node_get_key(avl_tree_node_t node);

/*
 * @brief Returns the height of current avl tree node.
 * Complexity O(1)
 *
 * @param AVL tree node
 * @see avl_tree_node_get_key
 */
DECLSPEC int avl_tree_node_get_height(avl_tree_node_t node);

/*!
 * @see binary_tree_new
 */
DECLSPEC avl_tree_t avl_tree_new(void *key);

/*!
 * @see binary_tree_delete_node
 */
DECLSPEC void avl_tree_delete_node(avl_tree_t avl);

/*!
 * @see binary_tree_delete
 */
DECLSPEC void avl_tree_delete(avl_tree_t avl);

/*!
 * @see binary_tree_compare_trees
 */
DECLSPEC int avl_tree_compare_trees(avl_tree_t avl1, avl_tree_t avl2, int compare(
		void *x, void *y, void *context), void *context);

/*!
 * @see binary_tree_is_empty
 */
DECLSPEC int avl_tree_is_empty(avl_tree_t avl);

/*!
 * @see binary_tree_is_leaf
 */
DECLSPEC int avl_tree_is_leaf(avl_tree_t avl);

/*!
 * @see binary_tree_get_size
 */
DECLSPEC int avl_tree_get_size(avl_tree_t avl);

/*!
 * @see binary_tree_get_root
 */
DECLSPEC avl_tree_t avl_tree_get_root(avl_tree_t avl);

/*!
 * @see binary_tree_get_key
 */
DECLSPEC void *avl_tree_get_key(avl_tree_t avl);

/*!
 * @see binary_tree_get_parent
 */
DECLSPEC avl_tree_t avl_tree_get_parent(avl_tree_t avl);

/*!
 * @see binary_tree_get_left_child
 */
DECLSPEC avl_tree_t avl_tree_get_left_child(avl_tree_t avl);

/*!
 * @see binary_tree_get_right_child
 */
DECLSPEC avl_tree_t avl_tree_get_right_child(avl_tree_t avl);

/*!
 * @see binary_tree_get_height
 */
DECLSPEC int avl_tree_get_height(avl_tree_t avl);

/*!
 * @see binary_tree_get_depth
 */
DECLSPEC int avl_tree_get_depth(avl_tree_t avl);

/*!
 * @see binary_search_tree_search
 */
DECLSPEC avl_tree_t avl_tree_search(avl_tree_t avl, void *key, int compare(void *x,
		void *y, void *context), void *context);

/*!
 * Complexity O(log(n))
 *
 * @param Adjust root
 * @see avl_tree_remove
 * @see binary_search_tree_insert
 */
DECLSPEC avl_tree_t avl_tree_insert(avl_tree_t *avl, void *key, int compare(void *x,
		void *y, void *context), void *context, int adjust_root);

/*!
 * Complexity O(log(n))
 *
 * @param Adjust root if user want this. It's used when you remove the key
 * from the tree's root and keeping the same pointer you won't be able to see the
 * whole AVL tree
 * @see binary_search_tree_remove
 * @return 1 if the key is found, 0 if not and -1 otherwise
 */
DECLSPEC int avl_tree_remove(avl_tree_t *avl, void *key, int compare(void *x, void *y,
		void *context), void *context, int adjust_root);

/*!
 * @see binary_search_tree_get_min
 */
DECLSPEC avl_tree_t avl_tree_get_min(avl_tree_t avl);

/*!
 * @see binary_search_tree_get_max
 */
DECLSPEC avl_tree_t avl_tree_get_max(avl_tree_t avl);

/*!
 * @see binary_tree_preorder
 */
DECLSPEC void avl_tree_preorder(avl_tree_t avl,
		void key_handler(void *x, void *context), void *context);
/*!
 * @see binary_tree_inorder
 */
DECLSPEC void avl_tree_inorder(avl_tree_t avl, void key_handler(void *x, void *context),
		void *context);

/*!
 * @see binary_tree_reverse_inorder
 */
DECLSPEC void avl_tree_reverse_inorder(avl_tree_t avl, void key_handler(void *x,
		void *context), void *context);

/*!
 * @see binary_tree_postorder
 */
DECLSPEC void avl_tree_postorder(avl_tree_t avl,
		void key_handler(void *x, void *context), void *context);

/*!
 * @see binary_tree_level_order
 */
DECLSPEC void avl_tree_level_order(avl_tree_t avl, void key_handler(void *x,
		void *context), void *context);

/*!
 * @see binary_tree_show_indented
 */
DECLSPEC void avl_tree_show_indented(avl_tree_t avl, void key_handler(void *x,
		int level, void *context), void *context);

/*!
 * @brief Debug utility
 * @param AVL tree
 * @param Key handler (key, height)
 * @param Debugging context
 */
DECLSPEC void avl_tree_debug(avl_tree_t avl, void key_handler(void *x, int height,
		int level, void *context), void *context);

#endif /* AVL_TREE_H_ */
